LIBKAKY
RESEARCH REPORTS ~mm
NAVAL POSTGRADUATE SCH
MONTEREY, CALIFORNIA 93i
NPS-55-86-010
NAVAL POSTGRADUATE SCHOOL
Monterey, California
TECHNICAL
DETERMINISTIC GRAPHICAL GAMES
ALAN R. WASHBURN
MAY 1986
Approved for public release: distribution unlimited
FedDocs
D 208.14/2
NPS-55-86-010
Prepared for:
val Postgraduate School
nterey, CA 93943-5000
.
NAVAL POSTGRADUATE SCHOOL
MONTEREY, CALIFORNIA
Rear Admiral R. H. Shumaker D. A. Schrady
Superintendent Provost
Reproduction of all or part of this report is authorized.
This report was prepared by:
L
XTiHirv m A^s.-n ATION O- 'H-S P^jt
mP L EVKNOXUBKAHV
REPORT DOCUMENTATION PAGE ^^LTOgTORADlWlg 8CHC
MOWEREV CA WW34jff
J"Rl ORT SECURITY CLASSlflCATION
UNCLASSIFIED
lb RESTRICTIVE MARKINGS
a. SECURITY CLASSIFICATION AUTHORITY
D DECLASSIFICATION /DOWNGRADING SCHEDULE
j DISTRIBUTION/ AVAILABILITY OF REPORT
Approved for public release; distribution
unl imited.
PERFORMING ORGANIZATION REPORT NUMBE R("s')
NPS55-86-010
5 MONITORING ORGANIZATION REPORT NUMBER(S)
j NAME OF PERFGRMiNU ORGANIZATION
Naval Postgraduate School
bD OFFICE SYMBOL
(If applicable)
Code 55
7d NAME OF MONITORING ORGANIZATION
c. ADDRESS {City. State, and ZIP Code)
Monterey, CA 93943-5000
7b. ADDRESS (dry. State, and ZIP Code)
j, NAME OF FUNDING /SPONSORING
ORGANIZATION
80 OFFICE SYMBOL
(// applicable)
9 PROCUREMENT INSTRUMENT IDENTIFICATION NUMBER
ADDRESS (City. State, and ZIP Code)
10 SOURCE OF FUNDING NUMBERS
PROGRAM
ELEMENT NO
D ROJECT
NO
TASK
NO.
WORK UNIT
ACCESSION NO
Title (inciuae Security Classification)
DETERMINISTIC GRAPHICAL GAMES
! PERSONAL AUTHOR(S)
Washburn. Alan R.
a. TYPE OF REPORT
Technical
13b. TIME COVERED
FROM TO
14. DATE OF REPORT (Year, Month, Day)
1986 Mav
15 PAGE COUNT
1-3
i SUPPLEMENTARY NOTATION
COSATI CODES
18 SUBJECT TERMS (Continue on reverse it necessary and identify by block number)
FIELD
GROUP
SUB-GROUP
Game, Chess, Graph
I ABSTRACT (Continue on reverse it necessary and identify by block numoer)
This paper gives a simple algorithm for solving a class of graphical games where
infinite play is possible.
) DISTRIBUTION/ AVAILABILITY OF ABSTRACT
_GQuNCLASSlFlED/UNLlMlTED D SAME AS RPT D OTIC USERS
21 ABSTRACT SECURITY CLASSIFICATION
UNCLASSIFIED
a NAME OF RESPONSIBLE INDIVIDUAL
Man R. Washburn
M
22b TELEPHONE (include AreaCoae)
408-646-2381
22c OFFICE SYMBOL
Code 55Ws
3 FORM 1473, aa mar
BJ APR coition may be used until e/nausted
All other editions are obsolete
SECURITY CLASSIFICATION OF THIS PAGE
DETERMINISTIC GRAPHICAL GAMES
Abstract
This paper gives a simple algorithm for solving a class
of graphical games where infinite play is possible.
Introduction
A Deterministic Graphical (DG) game is a two person zero sum game
played on a directed graph with n > nodes. Nodes are of two kinds:
terminal and continuing. Terminal nodes are those with no successors, and
have a payoff to player 1 associated with them. Continuing nodes have at
least one successor, and are labelled to indicate which player chooses the
successor. Play begins at some specified node, and continues until a
terminal node is reached. If no terminal node is ever reached, the payoff
is by convention 0. Our main intention in this paper is to describe an
algorithm for solving DG games in o(n 3 ) steps.
The reader may not welcome our introduction of a new term for what may
seem like a familiar class of games. However, DG games are actually a
slightly new topic. The deterministic Perfect Information games of von
Neumann and Morgenstern (1944) and also Kuhn (1953) are restricted to be
trees, which makes them a special case. It is true that DG games for which
infinite play is impossible (tic-tac-toe is a good example) can always be
put in the form of a tree by replicating nodes, but that operation can
greatly increase the number of nodes. Besides, there are interesting DG
games for which infinite play is possible. Chess is one of these; the
FIDE rules (Harkness, 1956) permit a draw to be demanded in certain cases
where no conclusion is in sight, but never force a draw merely on account of
game length. The Perfect Information games of Berge (1957, 1962) are closer
to DG games, but differ in that the payoff is influenced by all positions
(nodes) encountered in play, rather than only the terminal node. Several
authors have studied games similar to DG games where only two or three
payoffs are possible (Zermelo (1912), Holladay (1957), Smith (1966)). Smith
(1966) even comments that games with many possible payoffs are in principle
solvable by any method that can solve games with only two. Nonetheless, the
DG class has heretofore been nameless.
DG games are interesting because they seem to be the largest class of
"games of perfect information" that simultaneously permits parsimonious
representation and efficient computation. The possibility of infinite play
is explicit in DG games, even though the representation of a DG game is
itself finite. This permits the parsimonious representation of games
wherein a position can be repeated, without resort to devices such as move
counters or additional rules that simply prohibit repetition. Introducing a
large limit on the number of moves typically does not change the value of a
game, but does have the effect of greatly expanding the number of nodes in
its graphical representation. Pultr and Morris (1984) show that prohibiting
repetitions complicates the computational problem in an essential way. The
most natural thing to do in the presence of potentially infinite play seems
to be to simply permit it, which is consistent with representation as a DG
game. DG games are solvable in polynomial time in spite of the possibility
of infinite play, as will be shown below.
The fact that the payoff for infinite play in a DG game is assumed to
be is not really restrictive, since the addition of any constant to all
the payoffs of a game is strategically neutral. The assignment of payoff
to infinite play is simply an analytical convenience.
We now offer the following formal
Definition : . A DG game is a directed graph with finitely many
nodes partitioned into three sets: S 1 (S 2 ) is the set of nodes
where player 1 (player 2) chooses the successor, and T is the set
of terminal nodes on which some real payoff function F is
defined. The successor function is r, with rx being empty if and
only if xeT.
Recursive Games and Solvability
DG games are special cases of Recursive Games. Everett (1957) has
therefore shown that all DG games have values, and, since the game element
corresponding to each node has a trivial minimax solution, that optimal
stationary strategies exist. Since the existence of stationary strategies
is guaranteed, we will omit the word "stationary" in what follows. A
strategy Oi for player 1 is then simply a choice of a successor node in Tx
for each xeS^ to be used at every opportunity if x arises more than once.
Strategies for player 2 are defined similarly.
Definition : If H is some subset of the nodes of DG, we say that DG is
solvable over H if there is a pair of strategies (a x ,a 2 ) and a real function
W defined on the nodes of DG such that if the initial node is xeH,
a) all successors of x will remain in H and the payoff will be
at least Wx as long as player 1 employs a lf and
b) all successors of x will remain in H and the payoff will be
at most Wx as long as player 2 employs o 2
DG will be said to be solvable if it is solvable over all nodes.
We wish to show that DG is solvable. Our method will be to show that
DG is solvable over T, and that the set of nodes for which DG is solvable
can always be expanded if it is incomplete. We will frequently take
advantage of the fact that, if properties a) and b) above hold for an
"initial" node xeH, they will also hold if node x is chosen any time before
the game terminates; this follows from the stationarity of the strategies
being considered.
Preparatory Lemmas
L emma 1
Suppose that DG is solvable over H, that T c H, and that there is some
node yeH for which rye H. Then the game is solvable over HU ty}.
Proof
Let o lf o 2 > and W solve DG over H, and suppose yeS 1 . We will modify
the strategies and extend W to include y, so that DG is solved over H {y}.
The extension is
Wy = max Wz ( 1 )
zeTy
If z is any maximizing node in (1), let a/ be identical to afj except that
player 1 maps y into z. Since o/ agrees with o x on H, o l * guarantees that
all successors of nodes in H will remain in H, and therefore the same thing
is true of nodes in Hij{y}. Furthermore, a x ' guarantees at least Wx for
xeH {y}; any exception would contradict the fact that o x guarantees Wx for
xeH. This establishes property a) for a l 1 and Hu(y). To establish
property b) for o 2 and H u(y}, we have only to note that rye H, which
guarantees that successors of y remain in Hu(y) (in H, in fact) regardless
of the strategy employed by player 1, and also note that Wy is defined to be
a maximum, which means that no payoff larger than Wy is possible from node y
as long as player 2 employs o 2 . This completes the proof of lemma 1 for the
case where yeS 1 . Since TcH, the only other possibility is that yeS 2 , in
which case take
Wy = min Wz (2)
zeTy
and define o 2 ' to be a 2 except that player 2 maps y into z. The rest of the
proof is similar.
Lemma 1 assumed the existence of a node yeH for which Tyc H. In the
next lemma, we assume that such a node does not exist.
Lemma 2
Suppose that DG is solvable over H, that TcH, and that H n ry is not
empty for any yeH. Then there exists some yeH for which the game is
solvable over Hu(y).
Proof: Let o x , a 2 , W solve the game over H. Since by assumption each
player has the option of mapping nodes in H into H, there are strategies Z x
for player 1 and Z 2 for player 2 with the properties that l l (Z 2 ) agrees
with Oi (o 2 ) on H and that Z x (Z 2 ) maps nodes in H into H . Furthermore,
nodes in H are not successors of nodes in H under either o t or o 2 , and
therefore Z lt £ 2 , W solves the game over H. Let
Q. = {(x,i) xeHOS , ieHnrx}; j = 1,2 (3)
J J
and let w t = max Wi, and w 2 = min Wi. (4)
(x.DeQj (x,i)eQ 2
If Qj (Q 2 ) is empty, let w t be any negative number (w 2 be any positive
number). Intuitively, w 1 is the best payoff in H obtainable by player 1
from anywhere in H, and similarly for w 2 and player 2. We will prove the
lemma in three cases.
Case 1 (w^O)
Let (y,z) be any maximizing pair in the definition of w x , let Wy = v 1 ,
and let o/ be a l except that o/ maps y into z. The proof that property a)
holds for o/ and Hufy! is as in lemma 1. On the other hand player 2 can
guarantee a payoff of at most Wy from y by employing £ 2 , since under that
strategy the payoff will not exceed w, if some successor node (necessarily a
choice of player 1) is in H, or (since H contains no terminal nodes) if
all successor nodes are in H. Since E 2 agrees with a 2 on H, property b)
holds for Z 2 and Hu{y}. Therefore a/, Z 2 > w solves G over Hu{y}.
Case 2 (w 2 ^0)
Let (y,z) be any minimizing pair in the definition of w 2 , let Wy = w 2 ,
and let o 2 ' be a 2 except that o 2 ' maps y into z. Then Z l , o 2 '» W solves G
over H^ {y}. The proof is similar to that of case 1.
Case 3 (w^O and w 2 >0)
In this case we can take Wy = for all y in H. £, , E 2 , W solves DG
over all nodes. Note that Z 1 guarantees at least from any node yeH
because
a) If player 2 employs any strategy for which some successor of y
is in H, o x and therefore l x guarantees a non-negative payoff.
b) If player 2 employs any strategy for which no successor of y is
in H, Z 1 guarantees a payoff of 0.
Similarly, E 2 guarantees a payoff of at most from any node in H, and this
completes the proof of Case 3 and Lemma 2.
DG Theorem
All DG games are solvable.
Proof: Let H = T, and Wx = Fx for xeT. Any DG game is evidently solvable
over H . If H does not include all nodes, either lemma 1 or lemma 2
applies, and hence the game is solvable over some set H x that strictly
includes H . In a similar manner we can generate H 2 , H 3 , etc. Since there
are only finitely many nodes, we must eventually encounter some H that
includes all nodes, which means that the game is solvable.
An Example
Figure 1 shows the solution of a DG game with 18 nodes. Squares
represent moves for the maximizer, and circles for the minimizer. All arcs
are oriented toward the right except for the two that are curved, which are
oriented to the left. The terminal nodes are marked with numbers that
CD
CD
Q
O
.— CO
ZD
CD
o
oo
indicate the payoff. The five non-terminal nodes from which the value is
non-zero have letter labels to indicate the order of computation. Lemma 1
applies to nodes a,b,c, and e, and case 1 of lemma 2 applies to node d.
Case 3 of lemma 2 applies to the other four nodes, which are the last nodes
to enter H and the ones from which optimal play is non-terminating.
Computational Considerations
A bound on the computational effort required for a DG game with n nodes
can be obtained by first observing that the essential operation in applying
either lemma 1 or 2 is that of comparing two values, one of which has a node
index. Let h be the number of nodes in the solved set H. A straightforward
implementation of the DG Theorem would involve a loop in which h is
incremented by one in every cycle until either case 3 of lemma 2 arises or
else h=n , whichever comes first. In the worst case, one would have to do a
comparison for every pair (x,y) where xeH and yeH, a total of h(n-h)
comparisons when the loop index is h. Summing on h , we obtain a bound of
n n
1 h(n^h) comparisons, which is approximately f h(n-h)dh=n 3 /6. The amount
h=0
of effort involved is therefore no worse than cubic in the number of nodes.
The n 3 /6 bound would presumably not be sharp for a careful implementation of
the DG Theorem, since making h(n-h) comparisons may very well permit the
addition of multiple nodes to H (all nodes x in H for which Tx H can be
added to H, for example), and other efficiencies are also possible.
Random Moves
There is no conceptual difficulty in introducing random moves into
graphical games. If finite, such games are still Recursive Games and
therefore have solutions with stationary strategies. However, the inclusion
of random moves seems to complicate the solution procedure in an essential
manner; there is apparently no feature to exploit that is not already
present in Recursive Games. This is the reason for excluding the
possibility of random moves in DG games. There are thus two classes of
graphical games for which a simple solution technique is available, DG games
being one and finite tree games (possibly with random moves) being the
other. Backgammon is an example of a game that lies in neither class.
In Practice
We have argued that DG games permit a parsimonious representation of
games such as Chess. It is clear that even a parsimonious representation
and a polynomial time algorithm will not help much in solving games as
complicated as the archtype, however. Without taking advantage of symmetry,
even the representation of tic-tac-toe as a DG game would be a formidable
task. The French Military Game (Gardner (1963.), Lucas (1895)) comes to mind
as an example of a non-trival parlor game solvable as a practical matter if
a determined practioner were to make repeated application of lemmas 1 and 2.
The main difficulty with parlor games is the work involved in translating
the rules into graphical notation, rather than the ensuing computations.
For large DG games expressed directly as graphs, the existence of a
polynomial time solution algorithm would be more significant.
10
References
Berge, C, Topological Games with Perfect Information, Contributions to the
Theory of Games, vol _3_, Princeton U. Press, Princeton, NJ, 1957,
pp 165-178.
Berge, C, The Theory of Graphs, Methuen and Co. Ltd., London, 1962.
Everett, H., Recursive Games, Contributions to the Theory of Games , vol 3,
Princeton U. Press, Princeton, NJ, 1957, pp 47-78.
Gardner, M., Mathematical Games, Scientific American, October 1963,
pp 1 24-1 26.
Harkness, K., The Official Blue Book and Encyclopedia of Chess , David McKay,
New York, 1956.
Holladay, J. C, Cartesian Products of Termination Games, Contributions to
the Theory of Games , vol 3, Princeton U. Press, Princeton, NY, 1957,
pp 189-200.
Kuhn , H. W., Extensive Games and the Problem of Information,
Contributions to the Theory of Games , vol 2, Princeton U. Press,
Princeton, NJ, 1953, PP 193-216.
Lucas, M. E. , Recreations Mathematiques , vol 3, Gauthier-Villars ,
Paris, 1895, pp 105-1 1 6.
Pultr, A., and F. L. Morris, Prohibiting Repetitions Makes Playing
Games Substantially Harder, Int. Journal of Game Theory 1 3 , 1984,
pp 27-40.
Smith, C. A. B. , Graphs and Composite Games, Journal of Comb. Theory 1_, 1966
pp 51-81.
von Neumann, J., and 0. Morgenstern, Theory of Games and Economic
Behaviour , Princeton U. Press, Princeton, NJ, 1944.
Zermelo, E. , Uber Eine Anwendung Der Mengenlehre Auf Die Theorie
Des Schachspiels. International Congress of Mathematicians, 5th,
Cambridge University Press, 1912.
1 1
DISTRIBUTION LIST
Professor F. L. Morris
School of Computer and Information Sciences
313 Link Hall
Syracuse University
Syracuse, NY 1 3210
Professor Martin Shubik
Cowles Foundation
Yale University
New Haven, CT 06520
Professor Guillermo Owen (Code 530n)
Mathematics Department
Naval Postgraduate School
Monterey, CA 939^3-5000
Library (Code 01 42)
Naval Postgraduate School
Monterey, CA 939^3-5000
Dr. Ales Pultr
Department of Mathematics
Charles University
Sokolovska 83,
Prague 8
CZECHOSLOVAKIA
Professor Matthew J. Sobel
College of Management
Georgia Instute of Technology
Atlanta, GA 30332
Professor Lyn Thomas
University of Edinburgh
Department of Business Studies
William Robertson Bldg.
50 George Square
Edinburgh EH895Y
UNITED KINGDOM
Professor Jerzy Filar
Mathematical Science Department
John Hopkins University
Baltimore, MD 21 218
12
Professor Alan Goldman 1
Mathematics Sciences Department
John Hopkins University
Baltimore, MD 21218
Professor William F. Lucas 1
1598 Beloit
Claremont, CA 9171 1
Professor David Blackwell 1
Statistical Laboratory
University of California - Berkeley
Berkeley, CA 9^720
Professor A. J. Jones 1
Department of Mathematics
Royal Holloway College
University of London
UNITED KINGDOM
Research Administration (Code 012) 1
Naval Postgraduate School
Monterey, CA 939^3-5000
Professor Alan R. Washburn (Code 55Ws) 10
Department of Operations Research
Naval Postgraduate School
Monterey, CA 939^3-5000
Center for Naval Analyses 1
2000 Beauregard Street
Alexandria, VA 2231 1
Operations Research Center, Room E40-1 64 1
Massachusetts Institute of Technology
Attn: R. C. Larson and J. F. Shapiro
Cambridge, MA 02139
Defense Technical Information Center 2
Cameron Station
Alexandria, VA 22314
13
DUDLEY KNOX LIBRARY
3 2768 00336440 7